package com.example.leetdemo.process;

import java.util.*;
import java.util.stream.Collectors;

public class Solution675 {


    /**
    * @Des 时间效率低 未通过
    * @Auther  xuexumin
    * @Date  2022/5/24 9:47
    */

    public int cutOffTree(List<List<Integer>> forest) {
        if (forest.get(0).get(0) == 0) {
            return -1;
        }
        int[][] temp = new int[forest.size()][forest.get(0).size()];
        List<int[]> que = new ArrayList<>();
        for (int i = 0 ; i < forest.size(); i++) {
            for (int j = 0; j < forest.get(i).size(); j++) {
                if (forest.get(i).get(j) > 1) {
                    que.add(new int[] {forest.get(i).get(j), i, j});
                }
                temp[i][j] = forest.get(i).get(j) > 2 ?  2 : forest.get(i).get(j);
            }
        }
        int min = 0;
        if (que.size() == 1 ) {
            return 0;
        }

        que = que.stream().sorted(Comparator.comparingInt(o -> o[0])).collect(Collectors.toList());
        Iterator<int[]> iterator = que.iterator();
        int[] left = iterator.next();

        min += bps(temp, new int[]{0, 0}, new int[] {left[1], left[2]}, 0, Integer.MAX_VALUE);
        temp[left[1]][left[2]] = 1;

        while (iterator.hasNext()) {
            int[] next = iterator.next();
            int step = bps(temp, new int[]{left[1], left[2]}, new int[] {next[1], next[2]}, 0, Integer.MAX_VALUE);
            if (step == Integer.MAX_VALUE) {
                return -1;
            } else {
                min += step;
            }
            temp[next[1]][next[2]] = 1;
            left = next;
        }
        return min;
    }

    private int bps(int[][] forest, int[] source, int[] target, int step, Integer last) {
        if (source[0] == target[0] && source[1] == target[1]) {
            return step;
        }
        if (last < step + 1) {
            return last;
        }
        int thisStep = Integer.MAX_VALUE;
        if (source[0] > 0 && forest[source[0] - 1][source[1]] > 0) {
            int temp = forest[source[0] - 1][source[1]];
            forest[source[0] - 1][source[1]] = 0;
            thisStep = Math.min(bps(forest, new int[] {source[0] - 1, source[1]}, target, step + 1, thisStep), thisStep);
            forest[source[0] - 1][source[1]] = temp;
        }

        if (source[0] < forest.length - 1 && forest[source[0] + 1][source[1]] > 0) {
            int temp = forest[source[0] + 1][source[1]];
            forest[source[0] + 1][source[1]] = 0;
            thisStep = Math.min(bps(forest, new int[] {source[0] + 1, source[1]}, target, step + 1, thisStep), thisStep);
            forest[source[0] + 1][source[1]] = temp;
        }

        if (source[1] > 0 && forest[source[0]][source[1] - 1] > 0) {
            int temp = forest[source[0]][source[1] - 1];
            forest[source[0]][source[1] - 1] = 0;
            thisStep = Math.min(bps(forest, new int[] {source[0], source[1] - 1}, target, step + 1, thisStep), thisStep);
            forest[source[0]][source[1] - 1] = temp;
        }

        if (source[1] < forest[0].length - 1 && forest[source[0]][source[1] + 1] > 0) {
            int temp = forest[source[0]][source[1] + 1];
            forest[source[0]][source[1] + 1] = 0;
            thisStep = Math.min(bps(forest, new int[] {source[0], source[1] + 1}, target, step + 1, thisStep), thisStep);
            forest[source[0]][source[1] + 1] = temp;
        }

        return thisStep;
    }

    public static void main(String[] args) {
//        Integer[][] ints = {{2,1,3},{0,0,4},{5,6,7}};
//        List<List<Integer>> list = new ArrayList<>();
//        for (int i = 0; i < ints.length; i++) {
//            list.add(Arrays.asList(ints[i]));
//        }
//
//        Solution675 solution675 = new Solution675();
//        System.err.println(solution675.cutOffTree(list));

//        PriorityQueue<int[]> queue  = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));
        List<int[]> queue = new ArrayList<>();
        queue.add(new int[] {2});
        queue.add(new int[] {10});
        queue.add(new int[] {6});
        queue.add(new int[] {8});
        queue.add(new int[] {7});
        queue.add(new int[] {6});
        queue.add(new int[] {5});
        queue = queue.stream().sorted(Comparator.comparingInt(o -> o[0])).collect(Collectors.toList());

        Iterator<int[]> iterator = queue.iterator();
        while (iterator.hasNext()) {
            System.err.println(iterator.next()[0]);
        }
        System.err.println();

        TreeMap treeMap = new TreeMap();
        treeMap.containsKey("1");

//        while (!queue.isEmpty()) {
//            System.err.println(queue.poll()[0]);
//        }
    }

}
